package org.niu.listnode;

public class OddEvenList {
    public ListNode oddEvenList (ListNode head) {
        // write code here
        ListNode newHead = new ListNode(-1);
        ListNode tail = newHead;
        ListNode p = head;
        int cnt = 0;
        while(p!=null){
            cnt++;
            if((cnt%2)==1){
                tail.next = new ListNode(p.val);
                p=p.next;
                tail=tail.next;
            }
            p=p.next;
        }
        p = head;
        cnt = 0;
        while(p!=null){
            cnt++;
            if((cnt%2)==0){
                tail.next = new ListNode(p.val);
                p=p.next;
                tail=tail.next;
            }
            p=p.next;
        }
        return newHead.next;
    }
}
